package top.minuy.algorithm.sort.heap;

import top.minuy.structure.tree.heap.MaxHeap;

/**
 * 堆排序
 *
 * @author Minuy
 * @time 11:23
 * @date 2021/9/18
 */
public class HeapSort {
    private HeapSort() {
    }

    /**
     * 堆排序，O(nlongn)级别，原始方法
     *
     * @param arr 数组
     * @param <E> 泛型支持
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        if (arr.length <= 1) {
            return;
        }

        // heapify
        for (int i = getParent(arr.length - 1); i >= 0; i--) {
            shiftDown(i, arr, arr.length);
        }

        // 取出
        for (int i = arr.length; i > 0; i--) {
            extractMax(arr, i);
        }
    }

    /**
     * 获取父节点索引
     *
     * @param index 当前索引
     * @return 父节点索引
     */
    private static int getParent(int index) {
        if (index <= 0) {
            throw new IllegalArgumentException("GetParent failed. " + index + " not have parent.");
        }
        return (index - 1) / 2;
    }

    /**
     * 获取左孩子索引
     *
     * @param index 当前索引
     * @return 左孩子索引
     */
    private static int getLeftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取右孩子索引
     *
     * @param index 当前索引
     * @return 右孩子索引
     */
    private static int getRightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 移出最大值，这里是把最大值移到末尾了。不删除
     *
     * @param arr  要处理的数组
     * @param size 当前没处理的长度
     * @param <E>  泛型支持
     */
    private static <E extends Comparable<E>> void extractMax(E[] arr, int size) {
        // 取出最大值
        swap(arr, size - 1, 0);
        // 下沉
        shiftDown(0, arr, size - 1);
    }

    /**
     * 下沉，如果左右孩子那个比当前大就交换位置，都大交换最大的那个孩子，对[0,size)所形成的最大堆中的index元素进行下沉操作
     *
     * @param index 当前孩子
     * @param arr   要处理的数组
     * @param size  数组未处理长度
     * @param <E>   泛型支持
     */
    private static <E extends Comparable<E>> void shiftDown(int index, E[] arr, int size) {
        int maxChild;
        while ((maxChild = getLeftChild(index)) < size) { // 存在左孩子，默认左孩子为大孩子
            // 如果存在右孩子，并且右孩子大于左孩子
            if (getRightChild(index) < size && arr[getRightChild(index)].compareTo(arr[maxChild]) > 0) {
                // 大孩子改为右孩子
                maxChild = getRightChild(index);
            }

            // 如果当前节点大于最大的孩子
            if (arr[index].compareTo(arr[maxChild]) > 0) {
                // 不用再处理了
                return;
            }

            // 否则，交换大孩子和当前节点
            swap(arr, index, maxChild);
            // 跟踪当前节点
            index = maxChild;
        }
    }



    public static <E extends Comparable<E>> void sort2(E[] arr) {
        MaxHeap<E> maxHeap = new MaxHeap<>();
        int i = 0;
        // 放入堆中
        for (; i < arr.length; i++) {
            maxHeap.add(arr[i]);
        }
        // 依次从堆中取出
        for (--i; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }

    /**
     * 交换元素
     *
     * @param arr 数组
     * @param i   元素1索引
     * @param j   元素2索引
     * @param <E> 泛型支持，可比较的
     */
    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
